1789B - Serval and Inversion Magic - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <deque>
#include <string>
#include <functional>

using namespace std;

typedef long long ll;
const int INF = 1e9;

void solve()
{
	int n;
	cin >> n;

	string s;
	cin >> s;

	int l = n / 2, r = (n + 1) / 2;
	if (n % 2 == 1)
	{
		r--;
	}
	else
		l--;

	int lt = l, rt = r;
	while (lt > 0 && rt < n)
	{
		if (s[lt] != s[rt])
			break;
		lt--;
		rt++;
	}

	bool flag = false;
	if (lt == 0 && rt == n - 1 && s[lt] == s[rt])
		flag = true;

	int lf = 0, rf = n - 1;
	while (lf < rf && !flag)
	{
		if (s[lf] != s[rf])
			break;
		lf++;
		rf--;
	}

	if (lf == l && rf == r && s[l] == s[r])
		flag = true;

	if (!flag)
	{
		int vis = rt - lf, len = rf - rt;
		for (int i = rt; i <= rf; i++)
		{
			if (s[i] == '1')
				s[i] = '0';
			else
				s[i] = '1';
		}

		flag = true;
		for (int i = 0; i < n; i++)
		{
			if (s[i] != s[n - i - 1])
				flag = false;
		}
	}

	if (flag)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	//cout << lt << rt << endl;
	//cout << lf << rf << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}